package com.sise.DP;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *      139. 单词拆分
 *
 *      给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 *
 *      拆分时可以重复使用字典中的单词。
 *      你可以假设字典中没有重复的单词。
 *
 *      输入: s = "leetcode", wordDict = ["leet", "code"]
 *      输出: true
 *      解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 *
 *      题解：
 *      dp[i] 代表字符串 s 的前 i 个字符串组成的字符串 s[0..i-1] 是否能够被空格拆分成若干个字典中出现的单词。在 s[0..i-1] 中类比状态转移方程，
 *      每次转移的时候 需要包含最后一个单词
 *
 *      如果 s[i+1 -> n] 是字典中的单词，那么想要成功，就需要依赖于 s[0 -> i] 是否为 true，故此状态转移方程为 dp[n] = dp[i] && wordDictSet=dp[i -> n] (这里使用的是包含)
 *      这里使用的是 Set，故此 wordDict 中的顺序是无所谓的，反正都会匹配。例如[code,leet]，到时候最先匹配匹配到的还是 leet，
 *
 */
public class _139_wordBreak {
    static public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet<>(wordDict);          // 将要匹配的字符串放入 wordDictSet 去重
        boolean[] dp = new boolean[s.length() + 1];                 // 创建 dp 数组
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {                               // 这里的 j 每次都从 0 开始，计算的是从 0 -> i 之间的可能值，符合最后的大 dp[] 所表达的状态转移方程
                if (dp[j]) {                                            // 这里最先判断的是当前 位置是否为 true，如果不是为 true，说明当前位置并不能被拆分成多个单词，所以不进入下一步判断，这里可以缩减为 dp[j] && contains 判断
                    String word = s.substring(j, i);                    // 当前区间是否包含这个 word，如果 dp[j] = true，当前区间也包含此 word，那么就设置 dp[i] = true
                    boolean contains = wordDictSet.contains(word);      // 由于单词不会重复，故此这里直接使用包含即可
                    if (contains) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("co");
        list.add("leet");
        list.add("de");
        System.out.println(wordBreak("leetcode", list));
    }
}
